package main

import "math"

func main() {
	//[704. 二分查找](https://leetcode.cn/problems/binary-search/)
	//[27. 移除元素](https://leetcode.cn/problems/remove-element/)
	//[977. 有序数组的平方](https://leetcode.cn/problems/squares-of-a-sorted-array/)
	//[LCR 008. 长度最小的子数组](https://leetcode.cn/problems/2VG8Kg/)
	//[59. 螺旋矩阵 II](https://leetcode.cn/problems/spiral-matrix-ii/)
}

// 704
func search(nums []int, target int) int {
	left, right := 0, len(nums)-1
	for left <= right {
		mid := (right-left)/2 + left
		if nums[mid] > target {
			right = mid - 1
		} else if nums[mid] < target {
			left = mid + 1
		} else {
			return mid
		}
	}
	return -1
}

// 27
func removeElement(nums []int, val int) int {
	i := 0
	for _, j := range nums {
		if j != val {
			nums[i] = j
			i++
		}
	}
	return i
}

// 977
func sortedSquares(nums []int) []int {
	i, j := 0, len(nums)-1
	res := make([]int, len(nums))
	for idx := 0; idx < len(nums); idx++ {
		left := nums[i] * nums[i]
		right := nums[j] * nums[j]
		if left < right {
			res[idx] = right
			j--
		} else {
			res[idx] = left
			i++
		}
	}
	return reverse(res)
}

func reverse(nums []int) []int {
	for i, j := 0, len(nums)-1; i < j; i, j = i+1, j-1 {
		nums[i], nums[j] = nums[j], nums[i]
	}
	return nums
}

// LCR 008
func minSubArrayLen(target int, nums []int) int {
	if len(nums) == 0 {
		return 0
	}
	ans := math.MaxInt32
	start, end := 0, 0
	sum := 0
	for end < len(nums) {
		sum += nums[end]
		for sum >= target {
			ans = min(ans, end-start+1)
			sum -= nums[start]
			start++
		}
		end++
	}
	if ans == math.MaxInt32 {
		return 0
	}
	return ans
}

func min(a, b int) int {
	if a > b {
		return b
	}
	return a
}

// 59
func generateMatrix(n int) [][]int {
	ans := make([][]int, n)
	for i := range ans {
		ans[i] = make([]int, n)
	}

	up ,down, left, right := 0, n-1, 0, n-1
	cur := 1
	for cur <= n*n {
		//填充最上一行
		for i:=left; i<=right; i++ {
			ans[up][i] = cur
			cur++
		}
		up++
		//填充最右一列
		for i:=up; i<=down; i++ {
			ans[i][right] = cur
			cur++
		}
		right--
		//填充最下一行
		for i:=right; i>=left; i-- {
			ans[down][i] = cur
			cur++
		}
		down--
		//填充最左一列
		for i:=down; i>= up; i-- {
			ans[i][left] = cur
			cur++
		}
		left++
	}
	return ans
}